package cn.whdream.datastructure.search;

import java.util.Arrays;

import cn.whdream.datastructure.sort.Util;

/**
 * 
 * @author blackjuly
 * 插值查找  要求数组有序 ，最好数字比较连续的情况下比较能够体现出和二分查找的优势,或者边界都有优势，自适应.......关键字分布均匀有优势
 */
public class InsertValueSearch {
	public static void main(String[] args) {
		int arr[] = Util.randomAfterSoft();//{60,65,70,89,90,100,123};
		System.out.println(Arrays.toString(arr));
		int index = insertValueSearch(arr, 0, arr.length-1, 0);
		if(index == -1) {
			System.out.println("没有找到");
		}else {
			System.out.println("坐标："+index);
		}
		
	}
	
	/**
	 * 自己的思路
	 * @param arr 数组
	 * @param left 坐标索引
	 * @param right 右边索引
	 * @param findVal 需要找到的值
	 * @return -1 没有找到 其他则是找到了
	 */
	private static int insertValueSearch(int[] arr, int left, int right, int findVal) {
		System.out.println("hello");
		if(left > right || findVal < arr[0]|| arr[arr.length-1] < findVal ) {
			return -1;
		}
		int mid = left + (right - left) * ((findVal - arr[left]) / (arr[right] - arr[left]));
		//相等则说明找到了
		if(arr[mid] == findVal) {
			return mid;
		}
		
		//中间值比找的值大，则缩小范围找 到 左边区域找    （ps:应该排除 mid的值）
		if(arr[mid] > findVal) {
			return insertValueSearch(arr, left, mid -1, findVal);
		}
		//缩小到右边找	
		return insertValueSearch(arr, mid+1, right, findVal);
	}
}
